#include <iostream>
#include <string>
using namespace std;


bool isInterleave(string s1, string s2, string s3) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function  
	if(s1.size() + s2.size() != s3.size())
		return false;
	// is substring
	if(s3.size() == 0)
		return true;
	bool res = false;
	if(s1.size() != 0 && s1[0] == s3[0]){
		res = res || isInterleave(s1.substr(1), s2, s3.substr(1)); 
	}
	if(res)
		return true;
	if(s2.size() != 0 && s2[0] == s3[0]){
		res = res || isInterleave(s1, s2.substr(1), s3.substr(1));
	}
	if(res)
		return true;
	return false;

}


bool isInterleave_1(string s1, string s2, string s3) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function  
	if(s1.size() + s2.size() != s3.size())
		return false;
	// is substring
	if(s3.size() == 0)
		return true;
	
	bool *logic = new bool[s1.size()+1];
	logic[0] = true;
	for(int i=1; i<=s1.size(); ++i){
		if(s1[i-1] == s3[i-1]){
			logic[i] = logic[i-1];
		}
		else{
			logic[i] = false;
		}
	}
	for(int j=1; j<=s2.size(); ++j){
		logic[0] = s2[j-1] == s3[j-1]? logic[0] : false;
		for(int i=1; i<=s1.size(); ++i){
			bool res = false;
			if(s1[i-1] == s3[i+j-1]){
				res = res || logic[i-1];
			}
			if(s2[j-1] == s3[i+j-1]){
				res = res || logic[i];
			}
			logic[i] = res;
		}
	}
	int final = logic[s1.size()];
	delete []logic;
	return final;

}




int main(){
	cout<<isInterleave_1("aabc","abad","aabadabc")<<endl;
	return 0;
}